package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 归并排序优化版
 * @author GaoFeng2017
 * @date 2020/7/20 10:51
 */
public class TopdownMergeSortV3 implements Sort {

    /** 数组进行合并的最小长度，如果小于这个值，则使用插入排序 */
    private static final int MERGE_MIN_LENGTH = 15;

    @Override
    public void sort(Comparable[] srcElements) {
        Comparable[] auxiliaryElements = new Comparable[srcElements.length];
        System.arraycopy(srcElements, 0, auxiliaryElements, 0, srcElements.length);
        this.sort(srcElements, auxiliaryElements, 0 , srcElements.length - 1);
    }

    private void sort(Comparable[] srcElements, Comparable[] auxiliaryElements, int beginIndex, int endIndex) {

        if (beginIndex >= endIndex) {
            return;
        }

        // 优化点1: 对于小数组，直接使用插入排序
        if (endIndex - beginIndex < MERGE_MIN_LENGTH) {
            // 这里为什么是auxiliaryElements，而不是srcElements，因为上一个方法需要将srcElements排序到auxiliaryElements，而上一个方法的srcElements是当前方法的auxiliaryElements
            this.insertionSort(srcElements, beginIndex, endIndex);
            return;
        }

        int mid = (beginIndex + endIndex) / 2;

        sort(auxiliaryElements, srcElements, beginIndex, mid);
        sort(auxiliaryElements, srcElements, mid + 1, endIndex);

        // 优化点2: 对于当前区间已经有序的元素不再进行合并
        // 这里为什么是判断srcElements，因为在merge方法中，srcElements总是排序到auxiliaryElements中，而srcElements可能是srcElements也可能是srcElements，总之，它的角色是固定的。
        if (SortUtil.less(auxiliaryElements[mid], auxiliaryElements[mid + 1])) {
            System.out.println("current interval is sorted");
            System.arraycopy(auxiliaryElements, beginIndex, srcElements, beginIndex, endIndex - beginIndex + 1);
            return;
        }

        this.merge(srcElements, auxiliaryElements, beginIndex, mid, endIndex);

    }

    private void insertionSort(Comparable[] elements, int beginIndex, int endIndex) {
        for (int i = beginIndex + 1; i <= endIndex; i++) {
            for (int j = i; j > beginIndex && SortUtil.less(elements[j], elements[j - 1]); j--) {
                SortUtil.exchange(elements, j, j - 1);
            }
        }
    }

    private void merge(Comparable[] srcElements, Comparable[] auxiliaryElements, int beginIndex, int mid, int endIndex) {

        // 这里为什么用srcElements排序到auxiliaryElements，因为srcElements的角色固定了。
        // 左右指针
        int leftIndex = beginIndex;
        int rightIndex = mid + 1;

        for (int i = beginIndex; i <= endIndex; i++) {
            if (leftIndex > mid) {
                srcElements[i] = auxiliaryElements[rightIndex++];
            } else if (rightIndex > endIndex) {
                srcElements[i] = auxiliaryElements[leftIndex++];
            } else if (SortUtil.less(auxiliaryElements[rightIndex], auxiliaryElements[leftIndex])) {
                srcElements[i] = auxiliaryElements[rightIndex++];
            } else {
                srcElements[i] = auxiliaryElements[leftIndex++];
            }
        }
    }

}
